package com.gupao.alg.alg34;

import java.util.Arrays;

public class Topic1_Merge2Array {
    /**
     * 两个数组合并问题
     * 任务：
     * 自行实现merge1，merge2和merge3三个方法
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr1 = new int[10];
        arr1[0] = 1;
        arr1[1] = 2;
        arr1[2] = 3;
        int[] arr2 = new int[]{2, 5, 6};

        int testMethod = 3;

        switch (testMethod) {
            case 1:
                merge1(arr1, 3, arr2, 3);
                break;
            case 2:
                merge2(arr1, 3, arr2, 3);
                break;
            case 3:
                merge3(arr1, 3, arr2, 3);
                break;
        }

        //打印方式1：使用toString方法，但是这样不能控制有效数据的长度
//        System.out.println(Arrays.toString(arr1));
        //打印方式2：自己设计一个打印方法
        printList("合并的结果为", arr1, 6);


    }

    /**
     * 方法1：先将两个数组拼接到一起，再排序，从而实现有序合并
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        if(m+n>10){
            try {
                throw new Exception("Out of the bounds");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        for(int i=0;i<n;i++){
            nums1[m+i]=nums2[i];
        }

        Arrays.sort(nums1,0,5);

    }

    /**
     * 方法2：两个数组从后向前逐步合并
     *
     * @param nums1    {1,2,3}
     * @param nums1_len  3
     * @param nums2    {2,5,6}
     * @param nums2_len  3
     * nums1: {1,2,2,3,5,6}
     */
    public static void merge2(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {
        int i = nums1_len;
        int j = nums2_len;
        while(i+j>0) {
            if (j > 0 && i > 0 && nums1[i-1] >= nums2[j-1]) {
                nums1[i + j - 1] = nums1[i-1];
                i--;
            } else if (j > 0 && i > 0 && nums1[i-1] < nums2[j-1]) {
                nums1[i + j - 1] = nums2[j-1];
                j--;
            } else if (j > 0 && i == 0) {
                nums1[i + j - 1] = nums2[j-1];
                j--;
            } else if (j == 0 && i > 0) {
                nums1[i + j - 1] = nums1[i-1];
                i--;
            }
        }

    }

    /**
     * 方法3：优化上面的方法2,主要是精简代码
     *
     * @param nums1
     * @param nums1_len
     * @param nums2
     * @param nums2_len
     */
    public static void merge3(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {
        int i=nums1_len;
        int j=nums2_len;
        int k=nums1_len+nums2_len;
        while(i>0&&j>0){
            if(nums1[i-1]>=nums2[j-1]){
                nums1[k-1]=nums1[i-1];
                i--;
            }else if(nums1[i-1]<nums2[j-1]){
                nums1[k-1]=nums2[j-1];
                j--;
            }
            k--;
        }
        while(i>0&&j==0){
            nums1[k-1]=nums1[i-1];
            k--;
            i--;
        }
        while(i==0&&j>0){
            nums1[k-1]=nums2[j-1];
            k--;
            j--;
        }



    }

    /**
     * 打印处理之后的结果
     *
     * @param msg  文本提示信息
     * @param arr  数组
     * @param size 输出信息的大小
     */
    public static void printList(String msg, int[] arr, int size) {
        System.out.println(msg);
        for (int i = 0; i < size; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}
